\section*{Results}

We simulated indexing human chromosome 1 with different configurations of seeds,
including homogeneous seeds ranging from 12-base to 24-base, heterogeneous
seeds with $\tau = 100$ and $L_{max} = 24$ and PatternHunter with weighted
pattern ``11101001010011011101"\cite{PatternHunter}. In this simulation, we assume all mappers use
permutation arrays. We further assume each location list pointer in the
permutation array occupies 4 bytes; each location in the location lists occupies
4 bytes and each entry in the extension table occupies 8 bytes (4 bytes for the
extension, as each base occupies 2 bits, and 4 bytes for the location list
pointer).

\begin{figure}[h]
\centering
\includegraphics[width=0.9\textwidth]{figures/MappingCostComp_B.pdf}
\caption{Mapping cost for different seed configurations for human chromosome 1.}
\label{fig:mappingcostres}
\end{figure}

Figure~\ref{fig:mappingcostres} shows the mapping cost of different seed
configurations.  Compared to short seeds (12-base), heterogeneous seeds reduce
the mapping cost by 14.8x; while compared to long seeds (20-base),
heterogeneous seeds reduce the mapping cost by 2.0x; Compared to PatternHunter,
heterogeneous seeds reduce the mapping cost by 7.6x. From this figure, we
conclude that heterogeneous achieves and exceeds the reduction of computation of
homogeneous long seeds.

\begin{figure}[h]
\centering
\includegraphics[width=0.7\textwidth]{figures/MemoryUsage_B.pdf}
\caption{Memory consumption for different seed configurations for human chromosome 1.}
\label{fig:memory}
\end{figure}

Figure~\ref{fig:memory} shows the memory overhead of the data structures of homogeneous
short seeds (12-base), heterogeneous seeds as well as PatternHunter. Since both
homogeneous short seeds and PatternHunter use 12-base to generate the
permutation array, they share the same memory overhead. 
In the case of heterogeneous seeds, only a slight increase of 1.5\% in the
memory consumption is observed, compared to homogeneous short seeds.
%Heterogeneous seeds slightly increase the memory overhead by 1.5\%. 
For homogeneous long seeds (20-base), since very few long-seed mappers use
full permutation array (which generates 4TB data), we only compare to the best
case where only non-empty long seeds are stored. Under the best case,
heterogeneous seeds still reduce the memory overhead of long seeds by 2x. In
real implementations of using long seeds, however, mappers usually use partial
permutation arrays which allow empty seeds. Assuming a 1:9 non-empty to empty
seeds ratio (which is already very high, according to
Figure~\ref{fig:emptyseed}), heterogeneous seeds provide 8.7x reduction in
memory consumption. 

\begin{figure}[h]
\centering
\includegraphics[width=0.9\textwidth]{figures/Workload_B.pdf}
\caption{The number of locations to verify of different
configurations of seeds to map 1 million 80-base read to human chromosome 1.
Long seeds (20-base and 24-base) and PatternHunter do not support mapping with
more than 3 errors (2 errors for 24-base seeds) for 80-base reads (this is
indicated by N/A in the graph).}
\label{fig:workload}
\end{figure}

We also simulated mapping 1 million 80-base long reads that are generated from
the human chromosome 1 back to the same chromosome. Figure~\ref{fig:workload} presents
the result of using short seeds (12-base) long seeds (20-base and 24-base),
heterogeneous seeds and PatternHunter. From the graph, we observe that
heterogeneous seeds on average reduce the number of locations to verify by
9.89x compared to short seeds (12-base), 1.29x compared to long seeds (20-base)
and 4.73x compared to PatternHunter while increasing the number by 1.7x compared
to 24-base long seeds. Moreover, hetergeneous seeds provide the same level of
error-tolerance as short seeds whereas long seeds (20-base and 24-base) and
PatternHunter cannot tolerate more than 3 errors (20-base can not tolerate more
than 2 errors) hence their result are not shown beyond 3 errors.

\input{./sections/6.tex}

\section*{Conclusion}

HTS platforms continue to evolve at a fast rate. New technologies are frequently
introduced that offer different strengths; each, however, has unique biases. The
current trend is to generate longer reads, with newer technologies such as the
nanopore sequencing, at the cost of increased error rates.

In this paper, we analyzed the effects of using different seed lengths on the
speed, memory-efficiency and error-tolerance of conventional mappers. We observe
that the few expensive short seeds in the lookup table severely reduce the speed
of the mapper. Based on the analysis, we proposed ``Heterogeneous Seeds" which
simultaneously use seeds with different lengths in a mapper, according to the
frequencies of the seeds in the reference genome.

With heterogeneous seeds, we approximate the massive reduction in computation
provided by long seeds while at the same time retaining the high
memory-efficiency and high error-tolerance provided by short seeds.
